import java.util.*;

/*
 RandomBot - an example bot that picks up one of his planets and send half of the ships 
 from that planet to a random target planet.

 Not a very clever bot, but showcases the functions that can be used.
 Overcommented for educational purposes.
 */
class State
{
	List<Planet> enemyPlanets;
	List<Planet> neutralPlanets;
	List<Planet> friendlyPlanets;
	int botPlayerID;
	Planet preActionSource;
	Planet preActionDest;
	State parentState;
	
	State (List<Planet> enemyPlanets, List<Planet> neutralPlanets, List<Planet> friendlyPlanets, int ID)
	{
		// This constructor is just for the top node
		parentState = null;
		this.enemyPlanets = enemyPlanets;
		this.neutralPlanets = neutralPlanets;
		this.friendlyPlanets = friendlyPlanets;
		botPlayerID = ID;
		preActionSource = null;
		preActionDest = null;
	}
	
	State (State parentState, int ID, Planet actionSource, Planet actionDest)
	{
		preActionSource = actionSource;
		preActionDest = actionDest;
		botPlayerID = ID;
		this.parentState = parentState;
		enemyPlanets = new ArrayList<Planet>();
		neutralPlanets = new ArrayList<Planet>();
		friendlyPlanets = new ArrayList<Planet>();
		
		int fleetSent = actionSource.NumShips() / 2;
		Planet newActionDest = null;

		for (Planet fp : parentState.friendlyPlanets)
		{
			Planet newPlanet = (Planet)fp.clone();
			if (fp == actionSource)
			{
				newPlanet.RemoveShips(fleetSent);
			}
			friendlyPlanets.add(newPlanet);
		}
		
		Boolean neutral = false;
		
		for (Planet np : parentState.neutralPlanets)
		{
			Planet newPlanet = (Planet)np.clone();
			if (np == actionDest)
			{
				newActionDest = newPlanet;
				neutral = true;
			}
			neutralPlanets.add(newPlanet);
		}
		
		for (Planet ep : parentState.enemyPlanets)
		{
			Planet newPlanet = (Planet)ep.clone();
			if (ep == actionDest)
			{
				newActionDest = newPlanet;
			}
			enemyPlanets.add(newPlanet);
		}
		
		Update();
		
		int shipsLeftover = newActionDest.NumShips() - fleetSent;

		if (shipsLeftover >= 0)
		{
			newActionDest.RemoveShips(fleetSent);
		}
		else
		{
			newActionDest.RemoveShips(newActionDest.NumShips());
			newActionDest.Owner(botPlayerID);
			newActionDest.AddShips(-shipsLeftover);
			
			if (neutral)
			{
				neutralPlanets.remove(newActionDest);
				friendlyPlanets.add(newActionDest);
			}
			else
			{
				enemyPlanets.remove(newActionDest);
				friendlyPlanets.add(newActionDest);
			}
		}
	}
	
	public int Heuristic()
	{
		// Returns an integer, whereas the more minus the worse, the more plus the better.
		int enemyFleet = 0;
		int enemyGrowth = 0;
		for (Planet ePlanet : enemyPlanets)
		{
			enemyFleet += ePlanet.NumShips();
			enemyGrowth += ePlanet.GrowthRate();
		}
		double enemyInfo = enemyFleet + enemyGrowth * 4; 
				
		int friendlyFleet = 0;
		int friendlyGrowth = 0;
		for (Planet fPlanet : friendlyPlanets)
		{
			friendlyFleet += fPlanet.NumShips();
			friendlyGrowth += fPlanet.GrowthRate();
		}
		double friendlyInfo = friendlyFleet + friendlyGrowth * 4;
		
		if (enemyInfo == 0)
		{
			return Integer.MAX_VALUE;
		} 
		else if (friendlyInfo == 0)
		{
			return Integer.MIN_VALUE;
		}
		else
		{
			return (int)(friendlyInfo - enemyInfo);
		}
	}
	
	private void Update()
	{
		for (Planet p : friendlyPlanets)
		{
			p.AddShips(p.GrowthRate());
		}
		
		for (Planet p : neutralPlanets)
		{
			p.AddShips(p.GrowthRate());
		}
		
		for (Planet p : enemyPlanets)
		{
			p.AddShips(p.GrowthRate());
		}
	}
}

public class BFBot {
	/*
	 * Function that gets called every turn. This is where to implement the strategies.
	 */
	static List<List<State>> stateTree;
	
	private static State ToState(PlanetWars pw)
	{
		State result = new State(pw.EnemyPlanets(), pw.NeutralPlanets(), pw.MyPlanets(), pw.MyPlanets().get(0).Owner());
		return result;
	}
	
	private static void BreadthFirstSearch(PlanetWars pw, int depth)
	{
		for (int i = 0; i < depth; i++)
		{
			
		}
	}
	

	public static void DoTurn(PlanetWars pw) {
    
    //notice that a PlanetWars object called pw is passed as a parameter which you could use
    //if you want to know what this object does, then read PlanetWars.java
		int searchDepth = 3;
		State currentState = ToState(pw);
		stateTree = new ArrayList<List<State>>();
		List<State> levelOneFloor = new ArrayList<State>();
		levelOneFloor.add(currentState);
		
		stateTree.add(levelOneFloor);
		
		int bestHeuristic = Integer.MIN_VALUE;
		State bestState = null;
		
		for (int i = 0; i < searchDepth; i++)
		{
			List<State> currentFloor = stateTree.get(i);
			List<State> nextFloor = new ArrayList<State>();
			boolean endStateFound = false;
			for (State state : currentFloor)
			{
				// Hier voor de huidige state alle mogelijke volgende States toevoegen aan nextFloor
				for (Planet myPlanet : state.friendlyPlanets)
				{ 
					for (Planet neutralPlanet : state.neutralPlanets)
					{
						State stateToAdd = new State(state, myPlanet.Owner(), myPlanet, neutralPlanet);
						nextFloor.add(stateToAdd);
						int heuristic = stateToAdd.Heuristic();
						if (heuristic == Integer.MAX_VALUE)
						{
							// Eindstaat gevonden, stoppen met zoeken
							endStateFound = true;
							break;
						}
						else if (heuristic > bestHeuristic)
						{
							bestHeuristic = heuristic;
							bestState = stateToAdd;
						}
					}
					
					if (endStateFound)
						break;
					
					for (Planet enemyPlanet : state.enemyPlanets)
					{
						State stateToAdd = new State(state, myPlanet.Owner(), myPlanet, enemyPlanet);
						nextFloor.add(stateToAdd);
						int heuristic = stateToAdd.Heuristic();
						if (heuristic > bestHeuristic)
						{
							bestHeuristic = heuristic;
							bestState = stateToAdd;
						}
					}
					if (endStateFound)
						break;
				}
				if (endStateFound)
					break;
			}
			stateTree.add(nextFloor);
			if (endStateFound)
				break;
		}
		
		while (bestState.parentState != currentState)
		{
			bestState = bestState.parentState;
		}
		
		// Nu is bestState dus de state in diepte 1, die leidt naar de beste state.
		Planet source = bestState.preActionSource;
		Planet dest = bestState.preActionDest;
		

    //create a source planet, if you want to know what this object does, then read Planet.java

    //create a destination plane

    //(1) implement an algorithm to determine the source planet to send your ships from
    //... code here

    //(2) implement an algorithm to deterimen the destination planet to send your ships to
    //... code here

		//(3) Attack
		if (source != null && dest != null) {
			pw.IssueOrder(source, dest);
		}
		
	}

	public static void main(String[] args) {
		String line = "";
		String message = "";
		int c;
		try {
			while ((c = System.in.read()) >= 0) {
				switch (c) {
				case '\n':
					if (line.equals("go")) {
						PlanetWars pw = new PlanetWars(message);
						DoTurn(pw);
						pw.FinishTurn();
						message = "";
					} else {
						message += line + "\n";
					}
					line = "";
					break;
				default:
					line += (char) c;
					break;
				}
			}
		} catch (Exception e) {

		}
	}
}
